﻿

class Sol101
{
    public bool IsSymmetric(TreeNode root)//迭代
    {

        List<TreeNode> list = new List<TreeNode>(); 
        list.Add(root);
        list.Add(root);//把root当成两个，这样后面才可以一次出来两个

        while (list.Count > 0)
        {

            TreeNode left = list[0]; 
            TreeNode right = list[1];
            list.Remove(left);
            list.Remove(right);
            //list.RemoveAt(0);
            if (left == null && right == null)
            {//1，两个孩子都空，true
                continue;//这里跳过本次循环，但是要把null从队伍里面拿出来，否则队伍一直不空 
            }
             
            if (left == null || right == null) return false;//2，两个孩子空一个，false
            if (left.val == right.val)
            {

               

                list.Add(left.left);
                list.Add(right.right);
                
                list.Add(left.right);
                list.Add(right.left);
            }
            else
            {
                return false;
            }
          


        }


        return true;

    }


    public bool IsSymmetric2(TreeNode root)//递归
    {
       return  check(root, root);

    }  
    public bool check(TreeNode left, TreeNode right)
    {
        if (left == null && right == null) return true;//1，两个孩子都空，true
        if (left == null || right == null) return false;//2，两个孩子空一个，false
        //3，两个孩子都不空

        if (left.val == right.val)
        {
            //return true;//不可以直接返回
            //还要判断孩子节点是否对称

            if(check(left.left, right.right)&& check(left.right, right.left))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        else
        {
            return false;
        }



    }


}

class Program101
{
       

    static void Main101(string[] args)
    {
        int[] preOrder = { 1, 2, 3, 4, 2,4, 3 };
        int[] inOrder = { 3,2,4,1,4,2,3 };

        Solution105 Solution105 = new Solution105();
        TreeNode root= Solution105.BuildTree(preOrder,inOrder);


        Solution105.levelOrder(root);
        Sol101 sol101 = new Sol101();
        bool res= sol101.IsSymmetric(root);
        Console.WriteLine(res);

    }
}